package com.formula.datastructure.question.graph;

import com.formula.datastructure.standard.graph.AdjMatrixGraph;
import com.formula.datastructure.standard.graph.Dijkstra;
import com.formula.datastructure.standard.graph.Floyd;
import com.formula.datastructure.util.DataUtil;

/**
 * 最短路径和最小生成树不同, 它是计算两点间的最短距离, 最小生成树选的边并不是两点间最短距离
 */
public class ShortestPath {
    public static void main(String[] args) {
        String[] data = DataUtil.genStrArr(6);
        DataUtil.printStrArr(data);
        AdjMatrixGraph graph = new AdjMatrixGraph(data);
        graph.edges[0][1] = 3;
        graph.edges[1][0] = 3;

        graph.edges[0][2] = 3;
        graph.edges[2][0] = 3;

        graph.edges[1][2] = 5;
        graph.edges[2][1] = 5;

        graph.edges[1][3] = 2;
        graph.edges[3][1] = 2;

        graph.edges[1][5] = 4;
        graph.edges[5][1] = 4;

        graph.edges[4][5] = 1;
        graph.edges[5][4] = 1;

        graph.edges[3][4] = 4;
        graph.edges[4][3] = 4;

        graph.edges[2][4] = 9;
        graph.edges[4][2] = 9;
        testDijkstra(graph);
        //testFloyd(graph);
    }

    private static void testFloyd(AdjMatrixGraph graph) {
        Floyd floyd = new Floyd();
        int[][] result = floyd.calPath(graph);
        DataUtil.print2Array(graph.edges, result.length);
        System.out.println();
        DataUtil.print2Array(result, result.length);
    }

    private static void testDijkstra(AdjMatrixGraph graph) {
        Dijkstra dijkstra = new Dijkstra();
        int[] result = dijkstra.calPath(graph, 0);
        for (int i = 0; i < result.length; i++) {
            System.out.println(i + ", distance:" + result[i] + " , prev:" + dijkstra.preNode[i]);
        }
    }
}
